package week02

// 329. 矩阵中的最长递增路径
// https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

func longestIncreasingPath(matrix [][]int) int {
	var ans = 0
	// 统计每个点入度
	var inDeg [][]int
	for x := range matrix {
		inDeg = append(inDeg, make([]int, len(matrix[x])))
	}
	for x := range matrix {
		for y := range matrix[x] {
			for dir := range dx {
				nx := x + dx[dir]
				ny := y + dy[dir]

				if !isValid(matrix, nx, ny) {
					continue
				}
				if matrix[nx][ny] > matrix[x][y] {
					inDeg[nx][ny] += 1
				}
			}
		}
	}
	ans = topsort(matrix, inDeg)
	return ans
}

func topsort(matrix, inDeg [][]int) int {
	var queue []*Depth
	for x := range inDeg {
		for y := range inDeg[x] {
			if inDeg[x][y] == 0 {
				queue = append(queue, newDepth(x, y, 1))
			}
		}
	}
	var maxx = 0
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		maxx = max(maxx, node.depth)

		for dir := range dx {
			nx := node.x + dx[dir]
			ny := node.y + dy[dir]

			if !isValid(matrix, nx, ny) {
				continue
			}
			if matrix[nx][ny] > matrix[node.x][node.y] {
				inDeg[nx][ny]--
				if inDeg[nx][ny] == 0 {
					queue = append(queue, newDepth(nx, ny, node.depth+1))
				}
			}
		}
	}
	return maxx
}

func newDepth(x, y, depth int) *Depth {
	return &Depth{
		x: x,
		y: y,
		depth: depth,
	}
}

type Depth struct {
	x, y int
	depth int
}

func isValid(matrix [][]int, x, y int) bool {
	return x >= 0 && y >= 0 && x < len(matrix) && y < len(matrix[x])
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

var dx = [4]int{0, 1, 0, -1}
var dy = [4]int{1, 0, -1, 0}